# -*- coding: utf-8 -*-
# @File      :1
# @Author    :liaogan
# @Datetime  :2023/3/21 11:04



"""
算法思路：

遍历输入字符串中的每个字符。
如果字符是左括号，将其压入栈中。
如果字符是右括号，则从栈中弹出一个左括号，如果弹出的左括号与该右括号不匹配，则返回false。
在遍历完成后，如果栈不为空，则表示有左括号未被匹配，返回false，否则返回true。
时间复杂度为$O(n)$，其中$n$为输入字符串的长度。

"""
#
# def isValid(s: str) -> bool:
#     stack = []
#     s = {')': '(', '}': '{', ']': '['}
#     for c in s:
#         if c in s:
#             if not stack or s[c] != stack.pop():
#                 return False
#         else:
#             stack.append(c)
#     return not stack
#
# s = input().strip()
# print(isValid(s))



"""
这是一个典型的栈的应用场景。我们可以遍历字符串s，每遇到一个左括号就将其入栈，
每遇到一个右括号就将栈顶元素弹出，并判断弹出的左括号是否和当前右括号匹配。
如果匹配则继续遍历，否则返回false。

时间复杂度为O(n)，空间复杂度为O(n)。其中n为字符串s的长度。
"""
def isValid(s):
    stack = []
    for c in s:
        if c in ('(', '[', '{'):
            stack.append(c)
        elif c == ')' and (not stack or stack[-1] != '('):
            return False
        elif c == ']' and (not stack or stack[-1] != '['):
            return False
        elif c == '}' and (not stack or stack[-1] != '{'):
            return False
        else:
            stack.pop()
    return not stack

print(isValid("()[]{}"))